The present invention relates to devices and systems for efficiently querying and identifying multiple items on a communication channel preferably using radio frequency identification, and more particularly to interrogation devices and systems that identify radio frequency identification transponders.
Radio Frequency Identification (RFID) is a technology that is used to locate, identify and track many different types of items, such as clothing, laundry, luggage, furniture, computers, parcels, vehicles, warehouse inventory, components on assembly lines, and documents. RFID transponders, such as illustrated by RFID tags 6 in FIG. 1, are used in much the same way as optical bar codes, identifying the item to which they are affixed as being a particular individual or as being part of specific group. Unlike bar codes, RFID transponders can be read even when they cannot be seen, and hence a xe2x80x9cdirect line of sightxe2x80x9d for transmitted RF energy 4 and reflected RF energy 8 is not required between interrogation device 2 and the transponder. Furthermore, the identification numbers of a multiplicity of transponders 6 can be read virtually simultaneously, with little or no effort on the part of the user to xe2x80x9caimxe2x80x9d the interrogation device at each and every transponder. Some RFID transponders can store information in addition to that used for identification. This additional information may also be re-programmable by the user. Information within the transponder is typically accessed by a process variously referred to in the art as xe2x80x9cscanning,xe2x80x9d xe2x80x9creading,xe2x80x9d or xe2x80x9cinterrogating.xe2x80x9d
RFID transponders are typically interrogated by a radio transceiver with some added intelligence to enable it to send and receive data in accordance with a communication protocol designed into the transponder. When interrogating one or more transponders, the transceiver transmits RF energy 4 to the transponder, and encodes information on the outgoing signal by modulating the amplitude, phase and/or frequency of the signal. The RFID transponder can receive this signal and interpret the information sent by the interrogating device, and may also then respond by sending information contained in reflected RF energy 8 back to the interrogating device.
RFID transponders are often classified as either active or passive. An active transponder is continuously powered by a battery or alternate power source. In contrast, a passive transponder obtains its power from the RF field imposed upon it by an RFID transponder interrogation device. A passive RFID transponder, therefore, must remain close enough physically to the interrogating device to obtain adequate power to operate its circuits. Typically, the range for a passive transponder will be less than that of an active transponder, given that the interrogating device is transmitting the same amount of RF power at the same frequency for both types of transponders.
RFID transponders may be constructed from discrete components on a circuit board or they may be fabricated on a single silicon die, using integrated circuit (IC) techniques and needing only the addition of an antenna to function. Transponders are generally designed to operate in one of a number of different frequency bands. Popular frequencies are centered around 125 kHz, 13.56 MHz, 915 MHz and 2.45 GHz. These particular frequencies are chosen primarily because regulations in many countries permit unlicensed operation in these bands, and the permitted transmission power levels are suitable for communicating with and/or providing power to the RFID transponders. Transponders operating at lower frequencies (e.g. 125 kHz and 13.56 MHz) generally require larger antennas, and typically employ inductive coupling via multiple-turn coils to achieve a small antenna size. High frequency transponders typically utilize electric field coupling via simple half-wavelength dipole antennas. For example, 2.45 GHz transponders can use simple paper-thin, printed-conductor antennas as small as 60 mm by 5 mm. In contrast, 125 kHz transponders typically use a coil antenna, usually either made of many loops of wire or of a foil spiral affixed to a substrate material. In low frequency transponders, both coils and printed spirals must be quite large in order to achieve an appreciable operating range. Examples of such transponders may be found in U.S. Pat. Nos. 4,654,658 and 4,730,188.
RFID transponders are typically identified by a number contained within a memory structure within each transponder. This memory structure may be programmed in a variety of ways, depending on the technology used to implement the memory structure. Some transponders may employ factory-programmable metal links to encode the ID. Others may employ one-time-programmable (OTP) methods, which allow the end user to program the ID. This is often referred to as Write Once, Read Many (WORM) technology, or as Programmable Read Only Memory (PROM). Both fusible links and anti-fuse technologies are used to implement this method of storage. Still other technologies allow the user to program and re-program the ID many times. Electrically Erasable Programmable Read Only Memory (EEPROM) and FLASH memory are examples of technologies that can be used to implement this type of access. The transponder ID number is typically stored in a binary format for ease of implementation, though other representations could be used.
When multiple RFID transponders are within range of the interrogating device, it is typically desired to be able to identify all of the transponders in the field. Once the transponders have been identified, their presence may be noted in a computer database. Following identification, each of the transponders may also be addressed individually to perform additional functions, such as the storing or retrieving of auxiliary data.
The ability of the system to efficiently identify the presence of a multiplicity of transponders is highly dependent upon the communications protocol used to interrogate the transponders. Among those familiar with the art, a protocol suitable for allowing multiple transponders to respond to an interrogation request is typically referred to as an xe2x80x9canti-collision protocol.xe2x80x9d The process of singling out one transponder for communication is typically referred to as the process of xe2x80x9cisolation.xe2x80x9d
Most anti-collision protocols communicate between an interrogation device and RFID transponders present in an RF field have relied upon pseudo-random number (PN) generators. PN generators are typically used to vary the time during which the transponders may respond, so as to eventually allow a response from each transponder to reach the interrogation device without colliding destructively with the response from another transponder. Examples of such protocols can be found in U.S. Pat. Nos. 5,537,105, 5,550,547, and 5,986,570.
A drawback of using PN generators is that it is difficult to predict the time required to identify all of the transponders in the field, given that a certain number of transponders are in the field; hence, the time required is non-deterministic, even when the identities of the transponders being read are known. The use of random or pseudo-random intervals also necessitates the use of large time gaps between transponder transmissions to decrease the likelihood of collision between the transponder transmissions. This slows down the transponder communication process and drastically decreases the number of transponders that can be identified during a given amount of time. Previous anti-collision protocols utilizing PN generators have claimed to have the ability to achieve sustained read rates of up to approximately 80 transponders per second. Some protocols can read a single transponder in as little as 1 ms, but as the number of transponders in the field multiplies, PN generator-based protocols decline in performance, significantly increasing the average per-tag read time required.
Non-PN generator-based protocols known to be available are described in U.S. Pat. Nos. 5,339,073 and 5,856,788. The methods described in these patents interrogate the identification in a bit-by-bit fashion. These methods allow many transponders to reply to an interrogation simultaneously, but in a way that the interrogation device can still determine whether or not at least one transponder responded.
The protocol described in U.S. Pat. No. 5,856,788 is similar to a protocol used to uniquely identify and automatically configure expansion cards presently common in personal computers (PCs) employing the Industry Standard Architecture (ISA) expansion bus (as described in the xe2x80x9cPlug and Play (PNP) ISA Specificationxe2x80x9d by Intel and Microsoft). The protocol described in U.S. Pat. No. 5,856,788 and the ISA PNP protocol are designed to interrogate a unique identification number in a bit-by-bit fashion. The interrogated device, which may be a transponder or a PC expansion card, responds to a request for a specific bit by returning a symbol for a logic one, if the respective bit is of a specific predetermined value (usually one). If the respective bit in the device is not of the specific predetermined value, no response is returned. Responses are designed such that many devices may respond simultaneously without interfering with one another. If a response is received, the interrogating device may then conclude that at least one device exists containing the predetermined value in the requested bit location. After receiving a response, the interrogation device will then command all transponders that did not respond to enter an idle state. If no response is received, the interrogation device must assume that a transponder with a zero in the bit position just interrogated may be present, and the next bit is then interrogated. This process is repeated for the remaining bits until a single transponder remains in a non-idle state. This transponder is then said to be isolated.
When no response is received by the interrogation device for any given bit being interrogated, the interrogation device cannot determine whether the lack of a response was due to the presence of a tag with a zero in the bit position just interrogated or to the complete absence of tags which are able to respond.
Hence, both the protocol described in U.S. Pat. No. 5,856,788 and that used by ISA PNP terminate once the reception of an ID number which consists of all zero-valued bits is detected. Any time an identification process is commenced, this xe2x80x9cphantomxe2x80x9d transponder ID number must always be read in order to terminate the identification process. Furthermore, should a transponder suddenly be removed from the communication medium during an interrogation, the interrogating device would then misinterpret the lack of responses during the remainder of the interrogation as being indicative of a value of zero for the remaining bits. Further verification must be performed to assure that the ID received is correct. This is obviously undesirable, and adds unnecessary overhead to the protocol. This method also does not lend itself well to applications utilizing ID numbers stored in non-binary formats.
The method described U.S. Pat. No. 5,339,073 is similar to that described in U.S. Pat. No. 5,856,788, but provides a time slot for each possible value in each field being interrogated. Each field can be considered to contain a single digit of the ID number of the transponder. For binary-valued fields, two time slots are provided. The provision of a response for all possible field values accommodates non-binary ID storage, and eliminates the necessity of reading an all-zero ID number as in the method of U.S. Pat. No. 5,856,788. This method requires that the sequence of field values, which led up to an interrogation resulting in transponders responding, be recorded and later retransmitted in order to select specific groups of transponders for further interrogation. This process is repeated until the ID number of each transponder has been completely determined. The retransmission process adds unnecessary overhead to the identification process.
A system for locating documents or other objects is disclosed in U.S. Pat. No. 5,936,527. The invention disclosed herein was designed for, and hence is well suited for application in such a system, as it provides for the rapid interrogation of large numbers of transponders in a short period of time.
A typical RFID interrogation device (which may be used with the present invention) is shown in FIG. 2, wherein circulator 12 sends a predetermined series of transmissions and a typical RFID transponder 6 (see FIG. 3) receives the transmission at antenna 28, which is coupled to receive circuit 32. The reception of RF energy, as illustrated in FIG. 3, also may be used to generate power via power generator 30, which supplies power for activating receive circuit 32, control circuit 36, ID memory 38, and transmit circuit 34 (i.e., the components of transponder/tag 6). ID memory 38 stores identification data, while control circuit 36 keeps track of the transmissions received and controls transmit circuit 34 to respond to a transmission when required, which may be based on a comparison with identification data stored in ID memory 38, etc.
As illustrated in FIG. 2, antenna 10 receives transponder reply transmission 8, which is coupled to band pass filter 14 in interrogation device 2. The filtered, received signal is demodulated and detected by control microprocessor 20 via receive down-converter 16 and demodulation circuit 18. Microprocessor 20 controls phase locked loop 22, which provides a carrier signal to down-converter 16 and modulator 24. Control microprocessor 20 provides the next transmission data to modulator 24 that is amplified by power amplifier 26 and coupled to circulator 12 to begin the interrogation response cycle anew.
The circuits described in connection with FIGS. 2 and 3 should be considered exemplary, and other general RF transceiver circuits also are known in the art. What distinguishes the present invention from known systems and methods, however, is the protocol, specifically the manner in which the interrogating system transmits interrogating signals to the transponder and the manner in which the transponder transmits reply signals back to the interrogating system. The language of the protocol is illustrated in timing diagrams in FIGS. 4 and 5, while the protocol for the interrogating system and the transponder is illustrated in flowcharts in FIGS. 6 and 7, respectively.
In accordance with the present invention, improved protocols and methods are provided for an interrogation device (hereafter xe2x80x9cinterrogating systemxe2x80x9d) to identify RFID transponders faster than conventional methods, thus allowing for increased scanning speed.
In a preferred embodiment of the present invention, a protocol is provided that may be used in conjunction with a passive RFID transponder made to operate in the 915 MHz and/or 2.45 GHz bands. This type of high frequency transponder typically consists of a small silicon die with receiving and transmitting circuitry, and a printed antenna bonded to the die, both of which are sandwiched between small pieces of plastic film, which protect the die and antenna. The interrogating system communicates with the RFID transponder by modulating the amplitude of the transmitted RF signal at specific time intervals. In a preferred embodiment, the modulation is effected by sharply attenuating the transmitted RF signal. The transponder communicates with the interrogating system by shorting its antenna at certain intervals in response to the RF attenuation. By shorting its antenna, the transponder causes a reflection, which in turn produces a disturbance in the field being radiated by the interrogating system. This is referred to in the art as xe2x80x9cbackscatterxe2x80x9d modulation.
The present invention provides a method for reading RFID transponders, which is not only faster than current conventional methods but is deterministic given a set of transponders to be read. These features allow one to determine exactly how much time is required to read a given number of transponders with known identities; they also allow one to arrive at mathematical expressions for upper and lower bounds for the time required to read a given number of transponders whose identities are unknown. Since random number generators are not used, the only random elements of the transponder-reading process are introduced by the fact that the transponder identities are not typically known a priori, and by the random nature of the RF communications channel, which is subject to range limitations and interference.
One of ordinary skill in the art should recognize that the protocol could also be applied over a wired communications channel, such as a computer bus or a computer network, to query the identities of objects connected to the communication channel medium. Error rates on wired channels are often low enough to be ignored, leaving only the unknown object identities to impose a random nature on the time required for the protocol to identify all objects on the channel.
In the field of RFID, it is often important to be able to read the ID numbers of a multiplicity of transponders as quickly as possible. In particular, for applications in which many transponders pass in front of a stationary reader, or in which the reader must pass over many stationary transponders, the speed with which transponders can be read and identified is a critical performance parameter. Clearly, the more items that can be processed per unit time, the more useful the system becomes. Applications such as document tracking, asset tracking, and luggage and parcel sorting may all benefit greatly from an increase in scanning speed. Thus, the present invention may serve to further enhance the value of distributed interrogation systems, such as the type described in the aforementioned U.S. Pat. No. 5,936,527.
The present invention uses an adaptation of a tree traversal algorithm to identify all transponders in the RF field. In the nomenclature of those skilled in the art of computer science, the algorithm can be referred to as a xe2x80x9cdepth-firstxe2x80x9d tree traversal. This type of algorithm is in contrast with a xe2x80x9cbreadth-firstxe2x80x9d tree traversal. The present invention offers an improvement over the method of U.S. Pat. No. 5,856,788, in that it provides a response for all objects being identified, regardless of the value of the bit being interrogated; it provides a novel improvement over the method of U.S. Pat. No. 5,339,073, which uses a breadth-first approach, in that it eliminates the need to retransmit most of the sequences of field values in the course of the interrogation process.
It should be apparent to one skilled in the art that the invention herein described is applicable to other applications and fields in which an unknown number of items may be present on a communication channel, and for which a need exists to uniquely query and identify each of the items present. The invention may be implemented on a communications channel which may be wired, or which uses wireless communication in the form of radio frequency, optical, or acoustic signals.
Accordingly, one object of the present invention is to provide improved systems and methods for reading RFID-type transponders that are faster than previous methods.
Another object is to provide systems and methods for reading RFID-type transponders that are deterministic given a set of transponders to be read.
A further object of the present invention is to provide improved systems and methods that perform the rapid interrogation of large numbers of RFID-type transponders in a short period of time.
Yet another object is to substantially increase scanning speed for RFID-type transponders.
Still another object is to allow many RFID-type transponders to reply to an interrogation simultaneously and provide a response for all objects being identified, regardless of the value of the bit being interrogated.
Another object of the present invention is to eliminate the need to retransmit most of the sequences of field values in the course of the interrogation process.